package org.example;

public class Main {
    //理解这个题。首先要会二叉树的三种遍历方式。先 、中、后序的遍历方式。
    // 本题使用了。双重递归。（第一重递归，解决的问题是：通过先序（根、左节点、右节点）遍历，取出A树的每个根节点。和B树的开始根节点。传入第二重递归。）
    // 第二重递归解决的问题是：判断A的某个节点，是否和B树中的节点相等：（如果当前A树传入的根节点和B的根节点相等，就递归比较当前节点的左节点和右节点。和当前B的左节点和右节点是否相等。）
    //直到 B树的叶子节点为null。或者A.val!=B.val 或者 A的叶子节点为null。递归结束。
    //又因为 题目要求B是A的子结构。所以B=null 作为A=null。结束递归条件的前面。（子结构可以是一部分，即中间的一段，上有父节点下有子节点）
    // 最后心得体会：做递归题目一定要先找到递归结束条件，并且把递归结束条件。写在代码的前几行。
    public static void main(String[] args) {
        // [3,9,20,null,null,15,7],
        TreeNode treeNode = new TreeNode(3);

        treeNode.left = new TreeNode(9);
        treeNode.right = new TreeNode(20);
        treeNode.right.left = new TreeNode(15);
        treeNode.right.right = new TreeNode(7);

        TreeNode treeNode2 = new TreeNode(3);
        treeNode2.left = new TreeNode(9);

        System.out.println(isSubStructure(treeNode,treeNode2));
    }

    public static boolean isSubStructure(TreeNode A, TreeNode B) {
        // 如果A和B都不为空，且A和B都不为null，则返回recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B)
        return (A != null && B != null) && (recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B));
    }

    // 判断A和B是否相交，即A和B是否有子结构
    static boolean recur(TreeNode A, TreeNode B) {
        // 如果B为空，则返回true
        if (B == null) {
            return true;
        }
        // 如果A为空或者A的值不等于B的值，则返回false
        if (A == null || A.val != B.val) {
            return false;
        }
        // 如果A和B有子结构，则返回recur(A.left, B.left) && recur(A.right, B.right)
        return recur(A.left, B.left) && recur(A.right, B.right);
    }

}